Now that we've seen why the $O(E \log V)$ approach is superior for most real-world scenarios, let's apply this powerful algorithm to a classic, practical problem: designing a cost-effective campus network.
- The goal is to connect all university buildings with fiber-optic cable while minimizing the total length used. This is a perfect use case for a Minimum Spanning Tree.
- We can model this problem as a graph:
- Each building is a vertex.
- Each potential cable path is an edge.
- The length (and cost) of each path is the edge weight.
- By running Prim's algorithm, we find the set of connections that links every building with the absolute minimum total cable length. The MST's total weight gives us the project's minimum cost.
Python Implementation (Prim's for Campus Network)
1import heapq
2
3# Campus map represented as an adjacency list
4# Buildings: A=Admin, B=Biology, C=Chemistry, D=Dining, E=Eng, F=Fine Arts
5campus_graph = {
6 'A': [('B', 4), ('C', 3)],
7 'B': [('A', 4), ('C', 1), ('D', 5)],
8 'C': [('A', 3), ('B', 1), ('D', 2), ('E', 6)],
9 'D': [('B', 5), ('C', 2), ('E', 8), ('F', 7)],
10 'E': [('C', 6), ('D', 8), ('F', 9)],
11 'F': [('D', 7), ('E', 9)]
12}
13
14def calculate_min_cable(graph, start_node):
15 mst = []
16 total_cost = 0
17 visited = {start_node}
18 # Priority queue stores (weight, node1, node2)
19 edges = [(w, start_node, neighbor) for neighbor, w in graph[start_node]]
20 heapq.heapify(edges)
21
22 while edges and len(visited) < len(graph):
23 weight, u, v = heapq.heappop(edges)
24 if v not in visited:
25 visited.add(v)
26 mst.append((u, v, weight))
27 total_cost += weight
28 for neighbor, w in graph[v]:
29 if neighbor not in visited:
30 heapq.heappush(edges, (w, v, neighbor))
31 return total_cost, mst
32
33min_cost, network_layout = calculate_min_cable(campus_graph, 'A')
34print(f"Minimum cable length required: {min_cost} meters")
35# print(network_layout)